Enterprise and cloud data centers can include tens of thousands of servers, providing petabytes of storage to a large number of users and applications. Moreover, as cloud services continue to grow rapidly, large-scale cloud storage systems are being built to serve data to billions of users around the globe. The primary goal for these systems is to provide scalable performance and high-availability data storage systems, while minimizing operational expenses, particularly the bandwidth cost of moving data in the storage system. However, diverse input/output (I/O) workloads can cause significant data imbalance across servers, resulting in hot spots, or servers/disk drives that are overburdened with a large number of I/O requests. Such hot spots may cause high delays to end users. As a result, these services typically shuffle terabytes of data per day to balance the load across clusters. Furthermore, the same challenge has been raised and actively discussed in the context of building databases on clouds. However, this solution either does not address dynamic load reconfiguration or assumes the source and target nodes of dynamic data migration are known by an object-relational database management system.
Moreover, prior techniques have aimed to solve these challenges individually. To address load imbalance, many techniques perform dynamic placement of individual data objects, or distribute objects randomly across the cluster, e.g., based on hashing. However, adaptively redistributing objects involves the knowledge of load patterns for billions of objects. Optimizing reconfiguration costs for these patterns calls for offline solvers, e.g., knapsack or linear programming-based solvers, to make migration decisions. However, as such optimization is inherently expensive, these approaches are suitable at a small scale and less effective when systems grow to a large scale. Meanwhile, approaches trading effectiveness to achieve scalability, for instance, by using a simulated annealing or an evolutionary algorithm, suffer from high reconfiguration costs.